/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-06-23 16:01:38
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-06-25 13:56:32
 * @FilePath     : \data-structure\BST.js
 * @Description  : 二叉搜索树(Binary Search Tree)
 */

const COMP = {
  less: -1,
  more: 1,
  equ: 0,
}

class Node { //节点类
  constructor(key) {
    this.key = key
    this.right = null
    this.left = null
  }
}

class BST { //二叉搜索树
  constructor() {
    this.root = null
  }
  // 插入
  insert(key) {
    if (this.root == null) {
      this.root = new Node(key)
    } else {
      this.#insertNode(this.root, key)
    }
  }
  #insertNode(node, key) {
    if (this.#compareFn(key, node.key) === COMP.less) {
      if(node.left === null){
        node.left = new Node(key)
      }else{
        this.#insertNode(node.left, key)        
      }
    } else {
      if(node.right === null){
        node.right = new Node(key)
      }else{
        this.#insertNode(node.right, key)        
      }
    }
  }
  #compareFn(a, b) {
    if (a === b) {
      return COMP.equ
    } else if (a < b) {
      return COMP.less
    } else if (a > b) {
      return COMP.more
    }
  }

  // 中序遍历
  inOrderMap(callback){
    this.#inOrderNodeMap(this.root, callback)
  }
  #inOrderNodeMap(node, callback){
    if(node != null){
      this.#inOrderNodeMap(node.left, callback)
      callback(node)
      this.#inOrderNodeMap(node.right, callback)
    }
  }

  // 先序遍历
  preOrderMap(callback){
    this.#preOrderNodeMap(this.root, callback)
  }
  #preOrderNodeMap(node, callback){
    if(node != null){
      callback(node)      
      this.#preOrderNodeMap(node.left, callback)
      this.#preOrderNodeMap(node.right, callback)
    }
  }

  // 后序遍历
  postOrderMap(callback){
    this.#postOrderNodeMap(this.root, callback)
  }
  #postOrderNodeMap(node, callback){
    if(node != null){
      this.#postOrderNodeMap(node.left, callback)
      this.#postOrderNodeMap(node.right, callback)
      callback(node)
    }
  }

  // 获取最小值
  min(){
    let current = this.root
    while(current != null && current.left != null){
      current = current.left
    }
    return current.key
  }
  // 获取最大值
  max(){
    let current = this.root
    while(current != null && current.right != null){
      current = current.right
    }
    return current.key
  }

  // 是否包含
  includes(key){
    return this.#searchNode(this.root, key)
  }
  #searchNode(node, key){
    if(node === null){
      return false
    }
    if(this.#compareFn(key, node.key) === COMP.less){
      return this.#searchNode(node.left, key)
    }else if(this.#compareFn(key, node.key) === COMP.more){
      return this.#searchNode(node.right, key)
    }else{
      return true
    }
  }

  // 删除节点(最难)
  remove(key){
    this.root = this.#removeNode(this.root, key)
  }
  #removeNode(node, key){
    if(node === null){ // 如果是一个空树直接返回null
      return null
    }
    if(this.#compareFn(key, node.key) === COMP.less){
      node.left = this.#removeNode(node.left, key)
      return node
    }else if(this.#compareFn(key, node.key) === COMP.more){
      node.right = this.#removeNode(node.right, key)
      return node
    }else{
      if(node.left == null && node.right == null){ // 如果只有一个孩子节点，则直接删除
        node = null
        return node
      }
      if(node.left == null){ // 如果只有左孩子，就用左孩子
        node = node.right
        return node
      }else if(node.right == null){ // 如果只有右孩子，就用右孩子
        node = node.left
        return node
      }
    }
    // 如果左右都有孩子，则找到右侧最小节点替换删除的节点，并删除最小节点
    let current = node.right
    while(current.left != null){
      current = current.left
    }
    node.key = current.key
    node.right = this.#removeNode(node.right, current.key)
    return node
  }
}

let myTree = new BST()
// myTree.insert(100)
// myTree.insert(20)
// myTree.insert(50)
// myTree.insert(30)
// myTree.insert(70)
// myTree.insert(110)
// myTree.insert(105)
// myTree.insert(125)
// myTree.postOrderMap((value)=>{
//   console.log(value.key)
// })
// console.log('-----------------------')
// myTree.postOrderMap((value)=>{
//   console.log(value)
// })
// console.log('-----------------------')
// console.log(myTree.min())
// console.log(myTree.max())
console.log('------------------------------')
myTree.insert(3)
myTree.insert(2)
myTree.insert(5)
// myTree.insert(4)
myTree.insert(6)

myTree.remove(3)
console.log(myTree.root)